package top101K.linkedList;

/**
 * @Author quan
 * @Description 删除链表的倒数第n个节点12345,n=2删除后变为1235
 * @Date 2023/7/29 21:58
 */
public class Demo9_RemoveNthFromEnd {
    /**
     * 思路：走到被删除节点的前一个位置，更改指向。自己做的，分情况有点复杂，不够简单。
     * @param head 链表头结点
     * @param n 要被删除的倒数第n个节点
     * @return 返回被删除第n个节点之后的自子链表长度
     */
//    public ListNode removeNthFromEnd (ListNode head, int n) {
//        int count = 0;
//        ListNode pre = head;
//        while (pre != null) {
//            count++;
//            pre = pre.next;
//        }
//        ListNode dummyHead = new ListNode(-1);
//        dummyHead.next = head;
    //如果链表长度是2并且删除的是最后一个节点，返回头结点
//        if(count ==2 && n ==1){
//            head.next = null;
//            return head;
    //如果只有一个节点，就直接删除返回null
//        }else if (count ==1 && n ==1) {
//            return null;
    //如果有两个节点但是删除头结点，就返回头结点的下一个节点
//        } else if (count <= 2 && n == 2) {
//            return dummyHead.next.next;
//        } else {
//            ListNode cur = dummyHead;
//            for (int i = 0; i < count - n; i++) {
//                cur = cur.next;
//            }
//            if (n == 1) {
//                cur.next = null;
//                return head;
//            }  else {
//                ListNode right = cur.next;
//                cur.next = right.next;
//                return dummyHead.next;//不清楚这里为什么写成cur.next就出错，理论上cur就是dummyHead的一个复制出来的指针
//            }
//        }
//    }


    /**
     * 巧解：双指针：
     * 让快指针比慢指针先走n步，当快指针走到null的时候，慢指针已经就走到了倒数n的位置
     * @param head 链表头结点
     * @param n 倒数第n个节点
     * @return 返回删除倒数第n节点之后的链表头结点
     */
//    public ListNode removeNthFromEnd (ListNode head, int n) {
//        //定义快慢指针
//        ListNode fast = head;
//        ListNode low = head;
//        //让快指针先走n步
//        for (int i = 0; i < n; i++) {
//            fast = fast.next;
//        }
//        //如果fast此时已经走到了null，说明n与链表长度相等，要删除的一定是第一个节点
//        //此时直接返回头结点的下一个节点。注意这里的n表示的是倒数第n个节点
//        if(fast == null){
//            return head.next;
//        }
//        //此时删除的一定不是头结点
//        //当fast节点的下一个走到null的时候，此时low一定走向倒数n个节点的前驱
//
//        while (fast.next != null){
//            fast = fast.next;
//            low = low.next;
//        }
//        //更改指向即可
//        low.next = low.next.next;
//        return head.next;
//    }
//
    public ListNode removeNthFromEnd (ListNode head, int n) {
        if(head == null) {
            return null;
        }
        int len = 0;
        ListNode p = head;
        while(p != null) {
            p = p.next;
            len++;
        }
        //如果删除的是头结点
        int t = len - n;
        if(t == 0) {
            return head.next;
        }
        //t是待删除的节点位置
        p = head;
        int i = 1;
        while(i < t) {
            i++;
            p = p.next;
        }
        p.next = p.next.next;
        return head;
    }
}
